package com.lisp.algorithm.c1e415;

public class MaxSubArray3 {

    /*
    int maxSum
    int start
    int end
    for i : 0->a.length {
        (maxSum, end)_i = maxSubFromI(a, i);
        
        if(maxSum_i > maxSum) {
            maxSum = maxSum_i;
            start = i;
            end = end_i;
        }
    }
    */
    
    public static void main(String[] args) {
        int a[] = {-1, 1, -2, 2, 1};
        maxSubArray(a);
    }
    
    private static void maxSubArray(int a[]) {
        int maxSum = Integer.MIN_VALUE;
        int start = 0;
        int end = 0;
        for(int i=0; i<a.length; i++) {
            int maxSum_i = Integer.MIN_VALUE;
            int sum_i = 0;
            int end_i = i;
            for(int j=i; j<a.length; j++) {
                sum_i = sum_i + a[j];
                if(sum_i > maxSum_i) {
                    maxSum_i = sum_i;
                    end_i = j;
                }
            }
            
            if(maxSum_i > maxSum) {
                maxSum = maxSum_i;
                start = i;
                end = end_i;
            }
        }
        
        System.out.println(String.format("start=%d, end=%d, sum=%d", start, end, maxSum));
    }
}
